package com.zdp.others;

/*
* 求一个字符串的最长回文子串
* */
public class Manacher {
    static int maxIndex = -1;
    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));
        System.out.println(manacher(str1));
        System.out.println(maxIndex);
    }
    // 处理字符串，加入特殊字符  #a#b#c#1#2#3#4#3#2#1#a#b#
    public static char[] manacherString(String str){
        char[] arr = str.toCharArray();
        char[] res = new char[str.length()*2 +1];
        // 加入特殊字符
        int index = 0;
        for(int i=0;i < arr.length;i++){
            res[index++] = '#';
            res[index++] = arr[i];
        }
        res[index] = '#';
        return res;
    }

    // manacher 算法
    public static int manacher(String str){
        char[] arr = manacherString(str);
        // 回文半径数组 ,半径长度不包含中心点本身
        int[] radius = new int[arr.length];
        // 回文右边界
        int pr = 0;
        // 回文右边界中心点
        int center = 0;
        // 最长的那个
        int maxLength = Integer.MIN_VALUE;
        // 开始计算
        for(int i=0;i<arr.length;i++){
            // 判断是否在回文右边界内部
            // 其实就是决定等下扩充时候的开始位置，无论是否在回文右边界内，都会进行扩充
            // 用 while 来 代替到if判断 多种情况
            radius[i] = pr>i?Math.min(radius[center*2-i],pr-i-1):0;
            // 无论是否在回文右边界内部，都进行一次扩充
            // 边界条件，判断是否越界
            while(i+radius[i]+1 < arr.length && i-radius[i]-1 >-1){
                if(arr[i+radius[i]+1] == arr[i-radius[i]-1]){
                    radius[i]++;
                }else{
                    // 不符合就退出
                    break;
                }
            }
            // 更新最右边界和中心点
            if(i+radius[i]>pr){
                pr = i+radius[i];
                center = i;
            }
            if(maxLength<radius[i]){ // 更新最长回文子串
                maxLength = radius[i];
                maxIndex = i;
            }
        }
        // 得到最长回文子串
        int i = maxIndex-maxLength;
        char[] res = new char[maxLength*2 +1];
        int index = 0;
        while(i<=maxIndex+maxLength){
            res[index++] = arr[i++];
        }
        System.out.println(res);
        String s = String.valueOf(res);
        s= s.replace("#","");
        System.out.println(s);

        return maxLength;
    }

    // 老师写的
    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length]; // 回文半径
        int index = -1; //回文右边界中心点
        int pR = -1; // 右边界
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1; //pR>i,说明i在回文右边界的里面，Math.min 这个则是看 i的回文半径是i到右边界 还是就是i'的回文半径 ===>就是看i'的回文半径有没有在大的回文半径里面
            //若不在回文右边界，就要从自身开始扩
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                //这边是不管你什么情况，都会去扩一下，前面是在处理不用扩的区域
                //将if else 问题变成while来处理
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }
}
